package everyday;

/**
 * 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
 * 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
 * 若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]
 * 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
 *
 * 给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
 * @author le
 */
public class FindMinNumInRotateArray
{
    public static void main(String[] args)
    {
        int[] nums = {4,5,6,7,0,1,2};
        System.out.println(searchIndex(nums, 0));
    }

    private static int findMin(int[] nums) {
        if (nums.length == 1){
            return nums[0];
        }
        int low = 0;
        int high = nums.length-1;

        while (low < high){

            int mid = (high + low)/2;
            if (nums[mid] < nums[high]){
                high = mid;
            }else if (nums[mid] > nums[high]){
                low = mid+1;
            }else{
                high -= 1;
            }
        }
        return nums[low];
    }

    private static int searchIndex(int[] nums, int target) {
        // 找到中断的点
        int index = 0;
        for (int i = 0;i < nums.length-1;i++){
            if (nums[i] > nums[i+1]){
                index = i;
            }
        }
        // 划分成两个区域 进行二分查找
        int low1 = 0;
        int high1 = index;
        int low2 = index+1;
        int high2 = nums.length-1;

        while(low1 <= high1){
            int mid1 = low1 + (high1 - low1) / 2;
            if (nums[mid1] < target){
                low1 = mid1 + 1;
            }else if (nums[mid1] > target){
                high1 = mid1 - 1;
            }else{
                return mid1;
            }
        }
        while(low2 <= high2){
            int mid2 = low2 + (high2 - low2) / 2;
            if (nums[mid2] < target){
                low2 = mid2 + 1;
            }else if (nums[mid2] > target){
                high2 = mid2 - 1;
            }else{
                return mid2;
            }
            System.out.println(low2);
            System.out.println(high2);
        }
        return -1;
    }

    private static boolean search(int[] nums, int target){
        int low = 0;
        int high = nums.length-1;
        int n = nums.length;
        if (n == 0) {
            return false;
        }
        if (n == 1) {
            return nums[0] == target;
        }
        while(low <= high){
            int mid = (low + high) / 2;
            if (target == nums[mid]){
                return true;
            }
            if (nums[low] == nums[mid] && nums[mid] == nums[high]){
                low++;
                high--;
            }else if (nums[low] <= nums[mid]){
                if (nums[low] <= target && nums[mid] > target){
                    high = mid -1;
                }else{
                    low = low + 1;
                }
            }else{
                if (target > nums[mid] && target <= nums[high]){
                    low = mid +1;
                }else{
                    high = high - 1;
                }
            }
        }
        return false;
    }
}
